package com.squirrel.michale;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/27 7:26 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode2096 {

    // LCA Lowest Common Ancestor  最小公共祖先
        String path = "";

    public String getDirections(TreeNode root, int startValue, int destValue) {
        path = "";
        String path1 = path;
        String path2 = path;
        dfs(root,startValue,new StringBuilder());
        dfs(root,destValue,new StringBuilder());

        char[] c1 = path1.toCharArray();
        char[] c2 = path2.toCharArray();
        int index = 0;
        // 找出公共路径
        while(index < c1.length && index < c2.length && c1[index] == c2[index]){
            index++;
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < c1.length-index; ++i){
            sb.append("U");
        }
        sb.append(path2.substring(index));
        return sb.toString();
    }

    // 找出根节点到目标节点的路径
    public boolean dfs(TreeNode root, int target, StringBuilder sb){

        if(root.val == target) {
            path = sb.toString();
            return true;
        }

        if(root.left != null){
            sb.append("L");
            if(dfs(root.left,target,sb)) return true;
            sb.deleteCharAt(sb.length()-1);
        }
        if(root.right != null){
            sb.append("R");
            if(dfs(root.right,target,sb)) return true;
            sb.deleteCharAt(sb.length()-1);
        }
        return false;
    }

}
